package com.yan_jiu_sheng.LeetCodeHot100.AC;

/**
 * https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked
 * 不会，参考题解：https://leetcode.cn/problems/jump-game-ii/solutions/36035/45-by-ikaruga
 *
 * @author yulongTian
 * @create 2024-07-16 14:54
 */
public class Test75 {
    public static void main(String[] args) {
//        int[] nums = {2, 3, 1, 1, 4, 1, 2, 3, 5, 7, 1, 1, 1, 1, 2, 3, 4, 1, 1, 1, 1};
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println(new Test75().jump(nums));
    }

    public int jump(int[] nums) {
        // 返回的答案
        int ans = 0;
        // 起跳点结束
        int end = 0;
        // 在起跳点范围内能够跳到的最远点
        int maxPos = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            // 时刻更新能跳到的最远点
            maxPos = Math.max(nums[i] + i, maxPos);
            // 起跳点范围结束，更新跳跃次数和下一个起跳点结束点
            if (i == end) {
                end = maxPos;
                ans++;
            }
        }
        return ans;
    }

}
